import java.util.ArrayList;
import java.util.Scanner;

public class SeqTable<T extends Comparable<T>> {
    protected ArrayList<ElemType<T>> elem; //数据元素存储空间基址
    protected int length;   //表长度
    //构造函数，用数组data中前n个元素初始化顺序表
    public SeqTable(T[] data,int n)
    {
        elem = new ArrayList<ElemType<T>>();
        ElemType<T> e;
        for (int i = 0; i < n; i++)
        {
            e = new ElemType<T>(data[i]);
            elem.add(i,e);
        }
        length = n;
    }
    //顺序查找
    public int Search_Seq(T key)
    {
        int i;
        ElemType<T> e = new ElemType<T>(key);
        elem.add(length,e);  //哨兵
        for ( i=0; elem.get(i).key.compareTo(key)!=0;++i);
        if (i<length)
        {
            return i;
        }
        else
        {
            return -1;
        }
    }

    /**
     * 折半查找
     * 在有序表中折半查找关键字等于key的元素
     * @param key
     * @return
     */
    public int Search_Bin(T key)
    {
        int low,high,mid;
        low = 0;
        high = length -1;
        while (low<=high)
        {
            mid = (low+high)/2;
            if (key.compareTo(elem.get(mid).key) == 0)
            {
                return mid;
            }
            else if (key.compareTo(elem.get(mid).key)<0)
            {
                high = mid - 1;
            }else
            {
                low = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int key,index;
        Integer[] data = new Integer[]{34,44,43,12,53,55,73,64,77};
        SeqTable<Integer> ST = new SeqTable<>(data,data.length);
        System.out.println("请输入待查找的关键字");
        Scanner sc = new Scanner(System.in);
        key = sc.nextInt();
        index = ST.Search_Seq(key);
        if (index == -1)
            System.out.println("找不到关键字为"+key+"的元素！");
        else
            System.out.println("关键字为"+key+"的元素在查找表索引号为："+index);
    }

    //顺序查找的优点是算法简单，对表结构无特殊要求，无论采用顺序存储结构，还是采用链式存储结构，也无论结点之间是否按关键字有序或无序，它都同样适用。
    // 顺序查找的缺点是查找效率较低，特别是当n 较大时，不宜采用顺序查找，而必须选用更优的查找方法。

    //折半查找的优点是比较次数较顺序查找要少，查找速度较快，执行效率较高。
    //缺点是表的存储结构只能为顺序存储，不能为链式存储，且表中元素必须是有序的。


}
